/*
 * @lc app=leetcode.cn id=16 lang=golang
 *
 * [16] 最接近的三数之和
 */

// @lc code=start

func threeSumClosest(nums []int, target int) int {
	length := len(nums)
	sort.Ints(nums)
	var result int
	maxVal, minVal := 50000, -50000
	for i := 0; i < length; i++ {
		for j := i + 1; j < length; j++ {
			for k := j + 1; k < length; k++ {
				val := nums[i] + nums[j] + nums[k]
				if val >= maxVal {
					break
				}
				if val <= minVal {
					continue
				}
				if val == target {
					return target
				}
				result = val
				if val > target {
					maxVal = val
					minVal = 2*target - val
				} else {
					minVal = val
					maxVal = 2*target - val
				}
			}
		}
	}
	return result
}

// @lc code=end

